// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

//回溯法
class Solution {
    public List<String> letterCombinations(String digits) {
        List<String>result = new ArrayList<>();
        if(digits.length()==0)
            return result;
        Map<Character,String>map = new HashMap<Character,String>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        backtrap(result,digits,map,0,new StringBuffer());
        return result;
    }
    public void backtrap(List<String>result,String digits,Map<Character,String>map,int index,StringBuffer buffer)
    {
        if(index==digits.length())
        {
            result.add(buffer.toString());
            return;
        }
        else{
            char a = digits.charAt(index);
            String b = map.get(a);
            int len = b.length();
            for(int i=0;i<len;i++)
            {
                buffer.append(b.charAt(i));
                backtrap(result,digits,map,index+1,buffer);
                buffer.deleteCharAt(index);
            }
        }
    }
}